1. Field of the Invention
The present invention relates to the design of wireless networks. More specifically, the present invention relates to a method and a system for facilitating loop-free ad-hoc routing in a wireless network.
2. Related Art
Recent developments in mobile computing devices and wireless network technology have led to the recent development of wireless ad-hoc networks. In a wireless ad-hoc network, each node can be mobile and has at least one radio interface. Moreover, wireless ad-hoc networks typically do not have central network infrastructure, such as cell towers and base stations as access points. This is a significant advantage at locations where fixed infrastructure is unavailable. Exemplary applications of wireless ad-hoc networks include tactical military applications and commercial vehicle-to-vehicle systems.
Routing poses a challenge in a wireless ad-hoc network, because the network topology can change. Typically, data packets are forwarded from source to destination by regular network nodes, instead of dedicated routers. Since each node can be mobile, a route can change dynamically. For example, a node may leave an existing route, causing the route to be obsolete. A node may also join an existing route, resulting in an additional route. Hence, it can be a challenging task to discover and maintain loop-free and stable routes in a wireless ad-hoc network.
The Internet Engineering Task Force (IETF) mobile ad-hoc networks (MANET) working group has proposed several ad-hoc routing schemes: Ad-hoc On-demand Distance Vector (AODV) routing, Optimized Link State Routing (OLSR), Topology Dissemination Based on Reverse-Path Forwarding (TBRPF), Dynamic Source Rouging (DSR), and Dynamic MANET On-demand (DYMO) routing. The TBRPF and OLSR schemes adopt link-state routing, where nodes exchange topology information and determine shortest paths based on the topology. However, both the TBRPF and OLSR schemes can produce routing loops.
AODV, DSR, and DYMO are on-demand routing schemes, under which nodes do not maintain routes for all destinations but only for those with existing traffic. In these schemes, nodes typically discover paths by flooding route requests (RREQ) in the network, which result in route replies (RREP). In DSR, each source node maintains complete path information to each in-use destination. When a path changes, the source uses a path-recovery technique to re-discover the path. Unfortunately, the route re-discovery technique in DSR has been shown to be prone to looping. Both AODV and DYMO use distance labels and sequence numbers to ensure loop-free routes. However, the route-recovery techniques used by AODV and DYMO often involve end-to-end path changes and hence can invalidate many potential loop-free paths. Other routing solutions, while providing localized repairs during a route recovery, are prone to problems such as oscillation, convergence failure, and label space overflow when a new node joins an existing path.
Hence, a need arises for a method and a system that provides loop-free ad-hoc routing without the problems described above.